package leecode.stringAndArray.String;

public class LongestPalindrome {
    public static void main(String[] args) {
        LongestPalindrome longestPalindrome = new LongestPalindrome();
        String answer = longestPalindrome.longestPalindromeSolution2("abayh");
        System.out.println(answer);
    }
    private String longestPalindromeSolution(String s){
        String s1 = new StringBuffer(s).reverse().toString();
        int [][] arr = new int[s.length()][s.length()];
        int length = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(i)==s1.charAt(j)){
                    if(i==0||j==0){
                        arr[i][j]=1;
                    }else{
                        arr[i][j]=arr[i-1][j-1]+1;
                    }

                    if(arr[i][j]>length){
                        int beforei = s.length()-i-1;
                        if(j==beforei+arr[i][j]-1){
                            length=arr[i][j];
                            end=i;
                        }

                    }
                }
            }
        }
        return s.substring(end-length+1,end+1);
    }
    
    public String longestPalindromeSolution2(String s){
        int start=0,end=0,answer=0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s,i,i);
            int len2 = expandAroundCenter(s,i,i+1);
            int len = Math.max(len1,len2);
            if(len>answer){
                answer=len;
                start = i-len/2;
                end = i+len/2;
            }
        }
        
        return s.substring(start,end+1);
    }

    private int expandAroundCenter(String s, int left, int right){
        while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;
    }
}
